﻿using LEDScreenLinkTool.Util;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Documents;
using System.Windows.Shapes;
using System.Xml.Linq;

namespace LEDScreenLinkTool.Model
{
    /// <summary>
    /// 屏灯板连线模型
    /// </summary>
    public class ScreenGridModel
    {
        /// <summary>
        /// 灯板计算得出的连线结果
        /// </summary>
        List<BaseRouter> routeList;
        /// <summary>
        /// 屏灯板组成集合
        /// </summary>
        LedBoard[] boardArray;
        /// <summary>
        /// 灯板总数
        /// </summary>
        int totalCount;
        /// <summary>
        /// 每行的灯板列数
        /// </summary>
        int colunmCount;
        /// <summary>
        /// 最后一行的灯板列数,
        /// 奇数列的最后一行,列数和上面其他行的列数不一样
        /// </summary>
        int lastRowColumns;
        /// <summary>
        /// 每列的灯板行数
        /// </summary>
        int rowCount;

        public ScreenGridModel()
        {
            colunmCount = 0;
            rowCount = 0;
            lastRowColumns = 0;
            totalCount = 0;
            routeList = new List<BaseRouter>();
            boardArray = new LedBoard[totalCount];
        }

        /// <summary>
        /// 屏灯板连线模型
        /// </summary>
        /// <param name="configItems"></param>
        /// <param name="columns"></param>
        /// <param name="rows"></param>
        public ScreenGridModel(List<ScreenConfigItem> configItems, int columns, int rows)
        {
            totalCount = configItems.Count;
            lastRowColumns = colunmCount = columns;
            rowCount = rows;
            if (rowCount * colunmCount < totalCount)
            {
                lastRowColumns = totalCount - (rowCount - 1) * colunmCount;
            }
            routeList = new List<BaseRouter>();
            boardArray = new LedBoard[totalCount];

            for (var i = 0; i < totalCount; i++)
            {
                LedBoard gridItem = new LedBoard();
                gridItem.SerialNo = i;
                var module = configItems.FirstOrDefault(s => s.ScreenId == i);
                if (module != null)
                {
                    gridItem.ModLeft = module.X;
                    gridItem.ModTop = module.Y;
                }
                boardArray[i] = gridItem;
            }
            //设置为左右弯曲连接模式
            GeneratePuzzleSimple(boardArray);
            //设置为上下左右可连接模式
            //GeneratePuzzle(boardArray);
        }

        /// <summary>
        /// 找出以四个角的灯板为起止点的所有连线
        /// </summary>
        /// <returns></returns>
        public List<SolutionLine> FindCornersConnectLine()
        {
            routeList.Clear();
            int leftUpSrId = 0, rightUpSrId = 0, leftDownSrId = 0;
            int rightDownSrId = totalCount - 1;
            //左下角
            var leftDownScreen = boardArray.Where(s => s.ModLeft == 0).OrderByDescending(s => s.ModTop).FirstOrDefault();
            if (leftDownScreen != null)
            {
                leftDownSrId = leftDownScreen.SerialNo;
            }
            //右上角
            var rightTopScreen = boardArray.Where(s => s.ModTop == 0).OrderByDescending(s => s.ModLeft).FirstOrDefault();
            if (rightTopScreen != null && rightTopScreen.SerialNo < totalCount - 1)
            {
                rightUpSrId = rightTopScreen.SerialNo;
            }
            //四个点的接线起止可能组合(排除了同一横边起止的组合)
            List<string> sr = new List<string>();
            if (rightUpSrId != leftDownSrId)
            {
                sr.Add($"{rightUpSrId}-{leftDownSrId}");
                sr.Add($"{leftDownSrId}-{rightUpSrId}");
            }
            if (leftUpSrId != rightDownSrId)
            {
                sr.Add($"{leftUpSrId}-{rightDownSrId}");
                sr.Add($"{rightDownSrId}-{leftUpSrId}");
            }
            if (leftUpSrId != leftDownSrId)
            {
                sr.Add($"{leftUpSrId}-{leftDownSrId}");
                sr.Add($"{leftDownSrId}-{leftUpSrId}");
            }
            if (rightUpSrId != rightDownSrId)
            {
                sr.Add($"{rightUpSrId}-{rightDownSrId}");
                sr.Add($"{rightDownSrId}-{rightUpSrId}");
            }
            //四个角的组合排序
            int[] orderArr = new int[] { leftDownSrId, leftUpSrId, rightUpSrId, rightDownSrId };
            sr = sr.Distinct().OrderBy(e =>
                     {
                         int begNo= Convert.ToInt32(e.Split('-')[0]);
                         var index = 0;
                         index = Array.IndexOf(orderArr, begNo);
                         if (index != -1) { return index; }
                         else
                         {
                             return int.MaxValue;
                         }
                     }).ToList();
            int lastNo = -1;
            List<SolutionLine> solutions = new List<SolutionLine>();
            for (int si = 0; si < sr.Count; si++)
            {
                var strArr = sr[si].Split('-');
                int beginNo = Convert.ToInt32(strArr[0]);
                int endNo = Convert.ToInt32(strArr[1]);
                if (lastNo != beginNo)
                {
                    //每个点的所有连线
                    lastNo = beginNo;
                    routeList.Clear();
                    LedBoard begin = boardArray.FirstOrDefault(p => p.SerialNo == beginNo);
                    GetPusslzeLines(begin, boardArray);
                }
                int rank1 = routeList.Count;
                //找出结束点是四个角的连线
                for (int i = 0; i < rank1; i++)
                {
                    var route = routeList[i];
                    if (route.rPoints[route.rPoints.Count - 1] == endNo)
                    {
                        SolutionLine sln = new SolutionLine();
                        for (int j = 0; j < route.rPoints.Count; j++)
                        {
                            sln.GridNos.Add(route.rPoints[j]);
                        }
                        solutions.Add(sln);
                    }
                }
            }
            return solutions;
        }

        /// <summary>
        /// 找出某个灯板的所有连线
        /// </summary>
        /// <param name="screenIndex"></param>
        /// <returns></returns>
        public List<SolutionLine> FindConnectLines(int screenIndex)
        {
            routeList.Clear();
            LedBoard begin = boardArray.FirstOrDefault(p => p.SerialNo == screenIndex);
            GetPusslzeLines(begin, boardArray);  
            int rank1 = routeList.Count;
            List<SolutionLine> solutions = new List<SolutionLine>();
            for (int i = 0; i < rank1; i++)
            {
                var route = routeList[i];
                if (route != null)
                {
                    SolutionLine sln = new SolutionLine();
                    for (int j = 0; j < route.rPoints.Count; j++)
                    {
                        sln.GridNos.Add(route.rPoints[j]);
                    }
                    solutions.Add(sln);
                }
            }
            return solutions;
        }

        #region private method
        /// <summary>
        /// 上下左右四向可连
        /// </summary>
        private void GeneratePuzzle(LedBoard[] gridArr)
        {
            for (int i = 0; i < gridArr.Length; i++)
            {
                LedBoard gridItem = gridArr[i];
                gridItem.ClinkNos = new List<int>();
                int topId = -1, bottomId = -1, leftId = -1, rightId = -1;
                int curRow = i / colunmCount;
                int curCol = i % colunmCount;
                bool isLastCol = false;
                if (curRow >= (rowCount - 1))
                {
                    curCol = i - (rowCount - 1) * colunmCount;
                    curRow = (rowCount - 1);
                    isLastCol = curCol == (lastRowColumns - 1);
                }
                else
                {
                    isLastCol = curCol == (colunmCount - 1);
                }
                if (curRow > 0)
                {
                    //有上方
                    if (curRow == (rowCount - 1) && lastRowColumns != colunmCount)
                    {
                        //两个3*1屏上方接一个屏*2
                        topId = i - curCol - colunmCount + curCol / 2;
                        gridItem.ClinkNos.Add(topId);
                    }
                    else
                    {
                        topId = i - colunmCount;
                        gridItem.ClinkNos.Add(topId);
                    }
                }
                if (curRow < (rowCount - 1))
                {
                    //有下方
                    if (curRow == (rowCount - 2) && lastRowColumns != colunmCount)
                    {
                        //一个屏下方接两个3*1屏
                        bottomId = i - curCol + colunmCount + curCol * 2;
                        gridItem.ClinkNos.Add(bottomId);
                        //最右的屏下方可能只有一个
                        bottomId += 1;
                        if (bottomId < totalCount)
                        {
                            gridItem.ClinkNos.Add(bottomId);
                        }
                    }
                    else
                    {
                        bottomId = i + colunmCount;
                        gridItem.ClinkNos.Add(bottomId);
                    }
                }
                if (curCol > 0)
                {
                    //有左方
                    leftId = i - 1;
                    gridItem.ClinkNos.Add(leftId);
                }
                if (!isLastCol)
                {
                    //有右方
                    rightId = i + 1;
                    gridItem.ClinkNos.Add(rightId);
                }

                //左右有点的,不能穿上下
                if (leftId >= 0 && rightId >= 0)
                {
                    gridItem.ClinkNos.Clear();
                    gridItem.ClinkNos.Add(leftId);
                    gridItem.ClinkNos.Add(rightId);
                }
            }
        }

        /// <summary>
        /// 简单遍历整行再弯曲
        /// </summary>
        private void GeneratePuzzleSimple(LedBoard[] gridArr)
        {
            for (int i = 0; i < gridArr.Length; i++)
            {
                LedBoard gridItem = gridArr[i];
                gridItem.ClinkNos = new List<int>();
                int topId = -1, bottomId = -1, leftId = -1, rightId = -1;
                int curRow = i / colunmCount;
                int curCol = i % colunmCount;
                bool isLastCol = false;
                if (curRow >= (rowCount - 1))
                {
                    curCol = i - (rowCount - 1) * colunmCount;
                    curRow = (rowCount - 1);
                    isLastCol = curCol == (lastRowColumns - 1);
                }
                else
                {
                    isLastCol = curCol == (colunmCount - 1);
                }
                if (curRow > 0)
                {
                    //有上方
                    if (curRow == (rowCount - 1) && lastRowColumns != colunmCount)
                    {
                        //两个3*1屏上方接一个屏*2
                        topId = i - curCol - colunmCount + curCol / 2;
                        gridItem.ClinkNos.Add(topId);
                    }
                    else
                    {
                        topId = i - colunmCount;
                        gridItem.ClinkNos.Add(topId);
                    }
                }
                if (curRow < (rowCount - 1))
                {
                    //有下方
                    if (curRow == (rowCount - 2) && lastRowColumns != colunmCount)
                    {
                        //一个屏下方接两个3*1屏
                        bottomId = i - curCol + colunmCount + curCol * 2;
                        gridItem.ClinkNos.Add(bottomId);
                        //最右的屏下方可能只有一个
                        bottomId += 1;
                        if (bottomId < totalCount)
                        {
                            gridItem.ClinkNos.Add(bottomId);
                        }
                    }
                    else
                    {
                        bottomId = i + colunmCount;
                        gridItem.ClinkNos.Add(bottomId);
                    }
                }
                if (curCol > 0)
                {
                    //有左方
                    leftId = i - 1;
                    gridItem.ClinkNos.Add(leftId);
                }
                if (!isLastCol)
                {
                    //有右方
                    rightId = i + 1;
                    gridItem.ClinkNos.Add(rightId);
                }

                //左右有点的,不能穿上下
                if (leftId >= 0 && rightId >= 0)
                {
                    gridItem.ClinkNos.Clear();
                    gridItem.ClinkNos.Add(leftId);
                    gridItem.ClinkNos.Add(rightId);
                }
            }
        }

        /// <summary>
        /// 计算起始点的连线数量
        /// </summary>
        /// <param name="node">起始点</param>
        /// <param name="total">整屏的灯板</param>
        private void GetPusslzeLines(LedBoard node, LedBoard[] total)
        {
            if (node == null)
            {
                return;
            }
            //Todo 只能在第一个点并行展开计算
            Parallel.ForEach(node.ClinkNos, (lineNo) => {
                RouterInfo route = new RouterInfo(node.SerialNo, total.Length);
                route.AddNo(node.SerialNo);
                route.AddNo(lineNo);
                try
                {
                    FindNextRoute(route, lineNo, total);
                }
                catch(InvalidOperationException ex)
                {
                    Debug.WriteLine(ex.Message);
                }
                route.RemoveNo(lineNo);
            });
        }

        /// <summary>
        /// 递归增加节点
        /// </summary>
        /// <param name="route"></param>
        /// <param name="lineNo"></param>
        /// <param name="total"></param>
        /// <exception cref="InvalidOperationException"></exception>
        private void FindNextRoute(RouterInfo route, int lineNo, LedBoard[] total)
        {
            LedBoard curGrid = total[lineNo];
            //遍历当前节点的所有相邻点
            foreach (var linkNo in curGrid.ClinkNos)
            {
                if (!route.ContainNo(linkNo))
                {
                    //增加相邻点
                    route.AddNo(linkNo);
                    //完成连线,将连线结果放到routeList集合
                    if (route.IsFinish())
                    {
                        BaseRouter answerNode = new BaseRouter();
                        int[] answerArr = new int[route.rLen];
                        route.rPoints.CopyTo(answerArr,0);
                        answerNode.rPoints = answerArr.ToList();
                        routeList.Add(answerNode);
                        if(routeList.Count> ParamStruct.KMaxModuleCount)
                        {
                            throw new InvalidOperationException("Exceed Length");
                        }
                    }
                    else
                    {
                        FindNextRoute(route, linkNo, total);
                    }
                    //移除相邻点
                    route.RemoveNo(linkNo);
                }
            }

        }

        #endregion


        /// <summary>
        /// 每一个灯板
        /// </summary>
        internal class LedBoard
        {
            /// <summary>
            /// 灯板序号
            /// </summary>
            public int SerialNo;
            /// <summary>
            /// 相邻的灯板号
            /// </summary>
            public List<int> ClinkNos;  
            /// <summary>
            /// 横向位置X
            /// </summary>
            public double ModLeft;
            /// <summary>
            /// 纵向位置Y
            /// </summary>
            public double ModTop;
        }



        /// <summary>
        /// 一条灯板连线
        /// </summary>
        internal class BaseRouter
        {
            /// <summary>
            /// 连线顺序
            /// </summary>
            public List<int> rPoints;
        }

        /// <summary>
        /// 寻找连线方法类
        /// </summary>
        internal class RouterInfo
        {
            public int sNo;
            public int rLen;
            public int cLen;
            public int[] rPoints;
            public bool[] disableArr;

            /// <summary>
            /// 构造函数
            /// </summary>
            /// <param name="no">起始点</param>
            /// <param name="len">连线节点数</param>
            public RouterInfo(int no, int len)
            {
                sNo = no;
                rLen = len;
                cLen = 0;
                rPoints = new int[len];
                disableArr= new bool[len];
                for(int i=0;i<len;i++ )
                {
                    rPoints[i] = -1;
                    disableArr[i]= false;
                }
            }

            /// <summary>
            /// 增加下一个节点
            /// </summary>
            /// <param name="no"></param>
            public void AddNo(int no)
            {
                if (no < rLen)
                {
                    disableArr[no] = true;
                    rPoints[cLen]=no;
                    cLen++;
                }
            }

            /// <summary>
            /// 删除指定节点
            /// </summary>
            /// <param name="no"></param>
            public void RemoveNo(int no)
            {
                if (no < rLen)
                {
                    disableArr[no] = false;
                    cLen--;
                    rPoints[cLen] = -1;
                }
            }

            /// <summary>
            /// 节点是否已存在
            /// </summary>
            /// <param name="no"></param>
            /// <returns></returns>
            public bool ContainNo(int no)
            {
                return (no < rLen)? disableArr[no] : true;
            }

            /// <summary>
            /// 长度是否满足设定值,满足则结束寻找
            /// </summary>
            /// <returns></returns>
            public bool IsFinish()
            {
                return cLen == rLen;
            }

        }
    }




}
